/*
题目: 水位上升的泳池中游泳
在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

https://leetcode.cn/problems/swim-in-rising-water/
 */
public class SwimInWater {
    int[] dir = new int[] {0, -1, 0, 1, 0};
    int[][] grid;
    int time = 0, minTime, n;
    public int swimInWater(int[][] grid) {
        // 双向广搜
        this.n = grid.length;
        this.grid = grid;
        if (n == 1) return 0;

        Queue<int[]> frontQue = new LinkedList<> ();
        Queue<int[]> backQue = new LinkedList<> ();
        // 从两头出发, 是否达到过 某个 坐标
        Set<String> frontSet = new HashSet<> ();
        Set<String> backSet = new HashSet<> ();

        frontQue.offer(new int[] {0, 0});
        frontSet.add(String.valueOf(0) + '.' + String.valueOf(0));
        backQue.offer(new int[] {n - 1, n - 1});
        backSet.add(String.valueOf(n - 1) + '.' + String.valueOf(n - 1));

        while (!frontQue.isEmpty() && !backQue.isEmpty()) {
            int ret = -1;
            if (frontQue.size() <= backQue.size()) {
                ret = update(frontQue, frontSet, backSet);
            } else {
                ret = update(backQue, backSet, frontSet);
            }

            if (ret != -1)  return time;
        }

        return time;
    }

    private int update(Queue<int[]> queue, Set<String> cur, Set<String> another) {
        int size = queue.size();
        minTime = Integer.MAX_VALUE;
        // 对于每一个 "新时间" 作为一个循环
        while (size -- > 0) {
            int[] top = queue.poll();
            // 当前格子可以游动
            if (grid[top[0]][top[1]] <= time) {
                if (bfs(queue, top, cur, another)) return time;
            } else {  // 当前格子没法游动
                queue.offer(top);
                // 优化
                minTime = Math.min(grid[top[0]][top[1]], minTime);
            }
        }
        time = minTime;  // 直接选取四周中水位最低的
        return -1;
    }

    private boolean bfs(Queue<int[]> queue, int[] top, Set<String> cur, Set<String> another) {
        for (int i = 0; i < 4; i ++) {
            int nextX = top[0] + dir[i];
            int nextY = top[1] + dir[i + 1];
            String nextStr = String.valueOf(nextX) + '.' + String.valueOf(nextY);
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || cur.contains(nextStr)) continue ;

            cur.add(nextStr);
            if (time >= grid[nextX][nextY]) {
                if (another.contains(nextStr) || bfs(queue, new int[] {nextX, nextY}, cur, another))  return true;
            } else {  // 过不去
                queue.add(new int[] {nextX, nextY});
                minTime = Math.min(minTime, grid[nextX][nextY]);
            }
        }

        return false;
    }
}
